from typing import Optional

from python.mypackage import ListNode


class Solution:
    """
    方法：双指针，快慢指针。快指针先走n步，然后快慢指针一起走，当快指针到达末尾时，慢指针的下一个节点就是要删除的节点。

    Args:
        head: Optional[ListNode] - 链表头节点
        n: int - 要删除的倒数第n个节点

    Returns:
        Optional[ListNode] - 删除指定节点后的链表头节点

    Time: O(N) - N为链表长度，需要遍历一次链表

    Space: O(1) - 只使用了常数个指针变量
    """
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        left = right = dummy = ListNode(next=head)
        for _ in range(n):
            right = right.next # 右指针先向右走 n 步
        while right.next:
            left = left.next
            right = right.next
        # 左指针的下一个节点就是倒数第 n 个节点
        left.next = left.next.next 
        return dummy.next